Processing units perform different types of branch instructions to redirect (or “branch”) a program flow to an instruction at an address indicated by the branch instruction. Types of branch instructions include unconditional branches that redirect the program flow to a predetermined target address, conditional branches that are “taken” to redirect the program flow to a target address if the condition is satisfied and “not taken” to continue sequential execution of instructions if the condition is not satisfied, call instructions that redirect the program flow to an address of a subroutine, return instructions that redirect the program flow from the subroutine to an address after the call instruction that initiated the subroutine, and indirect branch instructions that redirect the program flow to different addresses depending on the state of the processing unit.
Branch prediction techniques are used to guess the outcome of a branch instruction so that the processing unit can begin speculatively executing subsequent instructions along the predicted branch before the processing unit has evaluated the branch instruction. The processing unit predicts the outcome using information in an entry of a branch prediction structure associated with a block of instructions that includes the branch instruction. If the predicted branch turns out to be incorrect when the branch instruction is evaluated, speculative execution along the incorrectly predicted branch is suspended and the state of the processing unit is rolled back to the state at the branch instruction to begin executing along the correct branch. More specifically, both the branch prediction unit and the fetch unit are rolled back to process from the correct target of the branch, or the address after the branch if the branch was not taken.